\relax 
\bibstyle{plain}
\citation{GibsonKT05}
\citation{GibsonKT05}
\citation{peleg}
\citation{DasSarmaHKKNPPW11}
\citation{NanongkaiSP11}
\citation{FrischknechtHW12}
\citation{peleg}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}}
\newlabel{sec:intro}{{1}{1}}
\citation{KuhnOM11}
\citation{KuhnOM11}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.1}Problem definition}{2}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces The distributed Edge Insert and Delete Model.}}{3}}
\newlabel{algo: model-general}{{1}{3}}
\@writefile{toc}{\contentsline {subsection}{\numberline {1.2}Our Results}{3}}
\citation{KS}
\citation{AC}
\citation{Charikar00}
\citation{BahmaniKV12}
\@writefile{toc}{\contentsline {section}{\numberline {2}Algorithm}{5}}
\newlabel{sec:algo}{{2}{5}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Main Algorithm}{5}}
\newlabel{sec:main}{{2.1}{5}}
\citation{KuhnLO10}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces {\sc  Maintain}($\epsilon $)}}{6}}
\newlabel{algo:maintain}{{1}{6}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Approximating the number of nodes and edges}{6}}
\newlabel{sec:counting}{{2.2}{6}}
\@writefile{toc}{\contentsline {section}{\numberline {3}Analysis}{6}}
\newlabel{sec:approx}{{3}{6}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {2}{\ignorespaces {\sc  Densest Subgraph}($k$)}}{7}}
\newlabel{algo:densest}{{2}{7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.1}Analysis for the densest subgraph problem}{7}}
\newlabel{theorem:approx densest}{{3.1}{7}}
\newlabel{lem: t prime prime to OPT}{{3.2}{7}}
\newlabel{eq:densest one}{{1}{7}}
\newlabel{eq:densest two}{{2}{7}}
\newlabel{eq:densest three}{{3}{8}}
\newlabel{eq:densest four}{{4}{8}}
\newlabel{eq:densest five}{{5}{8}}
\newlabel{obs:43}{{3.3}{8}}
\newlabel{lem:45}{{3.4}{8}}
\citation{KS}
\citation{KS}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2}Analysis for the at-least-$k$ densest subgraph problem}{9}}
\newlabel{thm:atleastktheorem}{{3.5}{9}}
\newlabel{lem:t prime prime to OPT for at least k}{{3.6}{9}}
\newlabel{eq:at least k one}{{6}{9}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {3}{\ignorespaces Defining $\ell $, $H^1, \ldots  , H^\ell $ and $D$ for the proof of Lemma\nobreakspace  {}3.6\hbox {}.}}{9}}
\newlabel{algo:algo for proof}{{3}{9}}
\newlabel{obs:48}{{3.7}{9}}
\newlabel{observation:proof of at least k}{{3.7}{9}}
\newlabel{eq:at least k one one}{{7}{10}}
\newlabel{eq:at least k one two}{{8}{10}}
\newlabel{eq:at least k one three}{{9}{10}}
\newlabel{eq:at least k one four}{{10}{10}}
\newlabel{eq:at least k one five}{{11}{10}}
\newlabel{eq:at least k two one}{{12}{10}}
\newlabel{eq:at least k two two}{{13}{10}}
\newlabel{eq:at least k two three}{{14}{10}}
\citation{KuhnLO10}
\citation{KuhnLO10}
\newlabel{eq:at least k two five}{{15}{11}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.3}Running Time Analysis}{11}}
\newlabel{sec:time}{{3.3}{11}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Counting the number of nodes and edges in a subgraph}{11}}
\newlabel{sec:count}{{4}{11}}
\citation{KuhnLO10}
\citation{AfekM94}
\@writefile{loa}{\contentsline {algorithm}{\numberline {4}{\ignorespaces \cite  {KuhnLO10}{\sc  RandomizedApproximateCounting}($V'$, $D$, $\epsilon $)}}{12}}
\newlabel{algo:kuhn}{{4}{12}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {5}{\ignorespaces {\sc  Count Nodes}($V'$, $D$, $\delta $)}}{13}}
\newlabel{algo:count nodes}{{5}{13}}
\citation{G84}
\citation{L}
\citation{AHI}
\citation{FKP}
\citation{K}
\citation{BCVGZ12}
\citation{KS}
\citation{KS}
\citation{AC}
\citation{KS}
\citation{Attiya-WelchBook}
\citation{lynch}
\citation{KuhnLO10}
\citation{peleg}
\citation{lynch}
\citation{peleg}
\citation{PK09}
\citation{elkin-survey}
\citation{dubhashi}
\citation{khan-disc}
\citation{khan-podc}
\citation{DasSarmaHKKNPPW11}
\@writefile{loa}{\contentsline {algorithm}{\numberline {6}{\ignorespaces {\sc  Count Edges}($V'$, $\epsilon $)}}{14}}
\newlabel{algo:count edges}{{6}{14}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Related Work}{14}}
\newlabel{sec:relatedwork}{{5}{14}}
\citation{AfekAPSController-FOCS87}
\citation{KormanKuttenControllerPODC07}
\citation{EmekKormanController-DISC09}
\citation{CidonS-IPL95}
\citation{AngluinSTOC80}
\citation{KuhnLO10}
\citation{AggarwalKuttenFST93}
\citation{MatiasA-WDAG89}
\citation{Berns09DissectingSelf-*}
\citation{Djikstra74SelfStabilizing}
\citation{DolevBookSelfStabilization}
\citation{KormanKMPODC11}
\citation{Kuhn2005-Repairing}
\citation{Poor-SelfHealQueue2003}
\citation{Ghosh07Self-healingSystemsSurvey}
\citation{PanduranganPODC11}
\citation{HayesFG-DCJournal-springerlink}
\citation{HayesPODC09}
\citation{Amitabh-2010-PhdThesis}
\bibdata{dense,selfheal}
\bibcite{AfekAPSController-FOCS87}{1}
\@writefile{toc}{\contentsline {section}{\numberline {6}Future Work and Conclusions}{15}}
\newlabel{sec:conc}{{6}{15}}
\bibcite{AfekM94}{2}
\bibcite{AggarwalKuttenFST93}{3}
\bibcite{AC}{4}
\bibcite{AngluinSTOC80}{5}
\bibcite{AHI}{6}
\bibcite{Attiya-WelchBook}{7}
\bibcite{BahmaniKV12}{8}
\bibcite{Berns09DissectingSelf-*}{9}
\bibcite{BCVGZ12}{10}
\bibcite{Charikar00}{11}
\bibcite{CidonS-IPL95}{12}
\bibcite{DasSarmaHKKNPPW11}{13}
\bibcite{Djikstra74SelfStabilizing}{14}
\bibcite{DolevBookSelfStabilization}{15}
\bibcite{dubhashi}{16}
\bibcite{elkin-survey}{17}
\bibcite{EmekKormanController-DISC09}{18}
\bibcite{FKP}{19}
\bibcite{FrischknechtHW12}{20}
\bibcite{Ghosh07Self-healingSystemsSurvey}{21}
\bibcite{GibsonKT05}{22}
\bibcite{G84}{23}
\bibcite{HayesFG-DCJournal-springerlink}{24}
\bibcite{HayesPODC09}{25}
\bibcite{khan-disc}{26}
\bibcite{khan-podc}{27}
\bibcite{K}{28}
\bibcite{KS}{29}
\bibcite{KormanKuttenControllerPODC07}{30}
\bibcite{KormanKMPODC11}{31}
\bibcite{KuhnLO10}{32}
\bibcite{KuhnOM11}{33}
\bibcite{Kuhn2005-Repairing}{34}
\bibcite{L}{35}
\bibcite{lynch}{36}
\bibcite{MatiasA-WDAG89}{37}
\bibcite{NanongkaiSP11}{38}
\bibcite{PK09}{39}
\bibcite{PanduranganPODC11}{40}
\bibcite{peleg}{41}
\bibcite{Poor-SelfHealQueue2003}{42}
\bibcite{Amitabh-2010-PhdThesis}{43}
